/**
* @description: 周赛306 t3
* @author hewei
* @date 2022/8/14 10:52
* @version 1.0
*/

public class SmallestNumber {

    StringBuilder stringBuilder;
    boolean[] flag;
    String ans = "";
    public String smallestNumber(String pattern) {

        flag = new boolean[10];
        for (int i = 1; i <= 9; i++) {
            stringBuilder = new StringBuilder();
            stringBuilder.append(i);
            flag[i] = true;
            process(pattern, 0);
            flag[i] = false;
        }
        return ans;
    }

    public void process(String s, int i) {
        if (i == s.length()) {
            if (ans.equals("") || stringBuilder.toString().compareTo(ans) < 0) ans = stringBuilder.toString();
            return;
        }

        char c = s.charAt(i);
        int temp = stringBuilder.charAt(i) - '0';
        if (c == 'I') {
            for (int j = temp; j <= 9; j++) {
                if (!flag[j]) {
                    stringBuilder.append(j);
                    flag[j] = true;
                    process(s, i + 1);
                    stringBuilder.deleteCharAt(stringBuilder.length() - 1);
                    flag[j] = false;
                }
            }
        } else {
            for (int j = temp - 1; j >= 1; j--) {
                if (!flag[j]) {
                    stringBuilder.append(j);
                    flag[j] = true;
                    process(s, i + 1);
                    stringBuilder.deleteCharAt(stringBuilder.length() - 1);
                    flag[j] = false;
                }
            }
        }
    }
}
